package org.hhchat.leetcode.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created this one by HMH on 2017/6/12.
 */
public class code368 {
    public static class Solution {
        public List<Integer> largestDivisibleSubset(int[] nums) {
            List<Integer> res = new ArrayList<>();
            if(nums.length==0) return Collections.emptyList();
            if(nums.length==1) {
                res.add(nums[0]);
                return res;
            }
            int[] count = new int[nums.length];
            int[] parent = new int[nums.length];
            Arrays.fill(parent,-1);
            Arrays.fill(count,1);
            Arrays.sort(nums);
            int max = 0;
            int k=0;
            for(int i=1;i<nums.length;i++) {
                for(int j=i-1;j>=0;j--) {
                    if (nums[i] % nums[j] == 0 && count[i] < count[j]+1) {
                        count[i]=count[j]+1;
                        parent[i]=j;
                    }
                }
                if(count[i]>max){
                    max=count[i];
                    k=i;
                }
            }
            for(int i=0;i<max;i++) {
                res.add(nums[k]);
                k=parent[k];
            }
            return res;
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.largestDivisibleSubset(new int[]{1,2,3}));
    }
}
